Recently, high performance of Internet switches and routers and reduction of power consumption have become urgent issues along with the advent of the era of cloud computing. In addition, there is a demand for a search engine that can perform a reliable search operation with higher speed and lower power consumption as a search engine for the Internet. In order to respond to such a demand, a CAM has been frequently used in Internet switches and search engines in recent years.
Here, search data called key data is input to the CAM at the time of searching data stored in the CAM. Further, when the same data as the key data is stored in the memory, the CAM outputs an address of a memory in which the key data is stored. The address at this time is also called an entry address. In general, it is necessary to access the entire memory space in the CAM in order to implement such a search function so that there is a problem that not only the circuit configuration becomes complicated but also the power consumption increases. In particular, this problem that the power consumption increases becomes severe as the scale of the CAM increases, and thus, is considered an extremely serious problem now.
In response to such a problem, for example, Patent Literature 1 proposes a data retrieval device aiming at low power consumption while making full use of high-speed retrieval performance of a CAM. The data retrieval device of Patent Literature 1 newly orders a plurality of pieces of rule data of which priorities are determined according to the order of data size, and allocates the plurality of pieces of rule data to a plurality of memory blocks according to the order. In addition, this retrieval device executes a search processing by specifying one memory block that should be searched at the time of performing retrieval of data. In this manner, the data retrieval device of Patent Literature 1 activates only the specified single block and does not need to activate the other blocks at the time of performing the search processing, and thus, it is considered that it is possible to reduce power consumption during the retrieval as compared to the typical CAM by such amount.
Although the data retrieval device disclosed in Patent Literature 1 described above can reduce the power consumption during the retrieval as compared with the typical memory, it is necessary to access the entire memory space in the block at once in order to execute the search processing. For this reason, the conventional data retrieval device has a problem that the circuit configuration is complicated and the power consumption during the retrieval is great. In this manner, the above-described technique of Patent Literature 1 does not present a fundamental solution to the current problem.
Therefore, a novel semiconductor device (CAM) has been proposed by the present inventors in order to implement data search at high speed and low power consumption (Patent Literature 2). This novel CAM is provided with a search memory mat in which an entry address corresponding to key data is written in a memory space specified by a memory address and a control circuit connected to the search memory mat. In the search memory mat, the memory space is divided into a plurality of separate memories. When the key data for a write to the search memory mat is input to the CAM, the control circuit divides the key data into a plurality of pieces of divided data. Then, the control circuit allocates the plurality of pieces of divided data to the plurality of separate memories, respectively, and writes the entry address corresponding to the divided data in the memory space specified by the memory address of each of the separate memories using each piece of the divided data as an address. In this manner, the entry addresses corresponding to the plurality of pieces of key data are written in the search memory mat.
In addition, a process of searching the key data written in the search memory mat is performed with the same steps as the write processing. That is, when key data as search target data is input to the CAM, the control circuit divides the key data as the search target data into a plurality of pieces of divided data. Then, the control circuit accesses the memory space specified by the memory address of each separate memory using each piece of the divided data as an address, and reads the entry address corresponding to the divided data from the accessed memory space.
In this manner, the key data is divided into a plurality of pieces, and the entry addresses corresponding to each piece of the divided key data are stored in the separate memories in the novel CAM developed by the present inventors. Therefore, it is unnecessary to make active (activate) the entire search memory mat at once at the time of searching this entry address, and it is possible to perform the search and partially activate the search memory mat for each separate memory. Therefore, it is possible to execute data search with much lower power consumption than the conventional CAM while implementing the data search with the same high-speed performance as the conventional CAM, according to the CAM of the present invention.